/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-28
 * Time: 23:38
 */



class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
//   思路:选择这个节点, 最大值就是左右子树都不选+当前节点的值 left[0]+right[0]+val
//       不选择这个节点,最大值就是,左右子树各自选与不选的最大值之和
//               max(left[0],left[1]) + max(right[0],right[1])
//       最后的结果就是根节点选与不选其中的较大值
//       使用后续遍历就可以先左右后根

    //后续遍历
    public int[] postOrder(TreeNode root){
        if(root==null){
            return new int[]{0,0};
        }
        int[] left=postOrder(root.left);
        int[] right=postOrder(root.right);
        int[] ret=new int[2];
        ret[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        ret[1]=left[0]+right[0]+root.val;
        return ret;
    }
    public int rob(TreeNode root) {
        int [] ans=postOrder(root);
        return Math.max(ans[0],ans[1]);
    }
}
